#ifndef LIST_H
#define LIST_H

#define LINKN linkNode<T>

namespace ePhys {

	template <class T>
	class linkNode {
	public:
		linkNode(T p) {
			before = 0;
			after = 0;
			me = p;
		}

		LINKN *before;
		T me;
		LINKN *after;
	};

	template <class T>
	class list
	{
	public:
		list(void) { first = last = _ptr = 0; size = 0; }
		~list(void) { empty(); }

		T operator[](unsigned int i) {
			unsigned int j = 0;

			//do this here because it slips throught the other ifs
			if(size == 1 && i == 0)
				return first->me;

			if(i >= size /2) {
				LINKN *p = last;
				j = size - 1;
				while(p != first)
					if(j--==i)
						return (T) p->me;
					else
						p = p->before;
			} else {
				LINKN *p = first;
				while(p != last)
					if(j++==i)
						return (T) p->me;
					else
						p = p->after;
			}
			return 0;// NULL;
		}

		unsigned int getIndex(T p) { 
			LINKN *c = first; unsigned int i = 0;
			while(c != last)
				if(p == (T)c->me)
					return i;
				else {
					c = c->after;
					i++;
				}
			return -1;		
		}

		void push_back(T p) {
			LINKN *s = new LINKN(p);
			size++;
			if(last) {
				last->after = s;
				last->after->before = last;
				last = last->after;
			} else
				first = last = s;
		}

		void push_front(T p) {
			squeeze(p, first);
		}

		void insert(T p, unsigned int i) {
			squeeze(p, nodeAt(i));
		}

		void remove(T p) {
			deleteNode(getNode(p));		
		}

		void removeAt(unsigned int i) {
			deleteNode(nodeAt(i));
		}

		void empty(void) {
			while(first) 
				deleteNode(first);
		}

		void startIter(void) {
			_ptr = first;
		}

		T next(void) {
			if(_ptr)
				if(_ptr->after) {
					_ptr = _ptr->after;
					return _ptr->before->me;
				} else {
					T r = _ptr->me;
					_ptr = 0;
					return r;
				}
			return 0;
		}

		T *makeArray(void) {
			T *a = new T[size];
			this->startIter();
			T p = this->next();
			int i = 0;
			while(p)
				a[i++] = p;
			return a;				
		}

		inline unsigned int getSize(void) { return size; }

	private:
		void deleteNode(LINKN *c) {
			if(c->before)
				if(c->after) {
					c->before->after = c->after;
					c->after->before = c->before;
				} else {
					last = c->before;
					c->before->after = 0;
				}
			else
				if(c->after) {			
					first = c->after;
					c->after->before = 0;
				} else
					first = last = 0;
			delete c; size--;
		}

		inline void squeeze(T s, LINKN *d) {
			LINKN *p = new LINKN(s);
			size++;
			if(d) {
				p->after = d;
				p->before = d->before;
				d->before = p;
				if(!p->before)
					first = p;
				else
					p->before->after = p;
			} else 
				first = last = p;		
		}

		inline LINKN *nodeAt(unsigned int i) {
			unsigned int j = 0;
			if(i >= size /2) {
				LINKN *p = last;
				j = size - 1;
				while(p != first)
					if(j--==i)
						return p;
					else
						p = p->before;
			} else {
				LINKN *p = first;
				while(p != last)
					if(j++==i)
						return p;
					else
						p = p->after;
			}
			return NULL;
		}

		inline LINKN *getNode(T p) {
			LINKN *c = first;
			while(c != last)
				if(p == (T)c->me)
					return c;
				else 
					c = c->after;
			return NULL;
		}

		LINKN *first, *last;
		unsigned int size;

		LINKN *_ptr;
	};

}

#endif